package LeetCode.Leet400_499.Leet490_499.Leet494;

/**
 * @ClassName Solution
 * @Author 孙天赐
 * @Date 2025/9/16 17:25
 * @Description TODO: 方法一   回溯  707ms   5.21%
 */
public class Solution_1 {
    int result = 0;
    int sum = 0;
    int[] nums;
    public int findTargetSumWays(int[] nums, int target) {
        this.nums = nums;
        doFindTargetSumWays(0, target);
        return result;
    }

    public void doFindTargetSumWays(int index, int target){
        if(index == nums.length){
            if(sum == target){
                result++;
            }
            return;
        }
        // +
        sum += nums[index];
        doFindTargetSumWays(index + 1, target);
        sum -= nums[index];

        // -
        sum -= nums[index];
        doFindTargetSumWays(index + 1, target);
        sum += nums[index];
    }
}
